//
// Created by guanyicheng on 2022/4/22.
//

#include "../../common.h"

class Solution {

private:

    void doReverse(string &s, long begin, long end) {
        while (begin < end) {
            char temp = s[begin];
            s[begin] = s[end];
            s[end] = temp;
            ++begin;
            --end;
        }
    }

    void rmBlank(string &s) {
        bool hasBlank = true;
        long fast = 0, slow = 0;
        while (fast < s.length()) {
            if (s[fast] != ' ') {
                hasBlank = false;
                if (fast > slow) {
                    s[slow] = s[fast];
                }
                ++fast;
                ++slow;
            } else {
                if (hasBlank) {
                    ++fast;
                } else {
                    hasBlank = true;
                    if (fast > slow) {
                        s[slow] = s[fast];
                    }
                    ++fast;
                    ++slow;
                }
            }
        }
        if (slow - 1 < s.length() && s[slow - 1] == ' ') {
            --slow;
        }
        s.resize(slow);
    }

public:
    string reverseWords(string s) {
        rmBlank(s);
        long fast = 0, slow = 0;
        doReverse(s, 0, s.length() - 1);
        while (fast < s.length()) {
            if (s[fast] == ' ') {
                doReverse(s, slow, fast - 1);
                slow = fast + 1;
            }
            ++fast;
        }
        doReverse(s, slow, s.length() - 1);
        return s;
    }
};

int main() {
    auto s = "  hello world  ";
    cout << Solution().reverseWords(s) << endl;
}